package com.leetcode.algs4.string;

import java.math.BigInteger;
import java.util.Random;

/**
 * @author Dennis Li
 * @date 2020/7/10 21:58
 */
public class RabinKarp {
    private String pat;
    private long patHash;
    private int M;
    private long Q;
    private int R;
    private long RM;

    public RabinKarp(String pat) {
        this.pat = pat;

        this.M = pat.length();
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i <= M - 1; i++) {
            RM = (R * RM) % Q; // 减去第一个数字时的计算
        }
        patHash = hash(pat, M);
    }

    private long hash(String key, int m) {
        long h = 0;
        for (int j = 0; j < m; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    private boolean check(int i) {
        return true;
    }

    // a random 31-bit prime
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }

    private int search(String txt) {
        int N = txt.length();
        long txtHash = hash(txt, M);
        // 一开始就匹配成功
        if (patHash == txtHash && check(0)) return 0;
        for (int i = 1; i < N; i++) {
            // 计算散列值
            //散列值的移位方式，先减去首位，再乘上RM，加上最后一个数字，再执行匹配
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            if (patHash == txtHash) {
                if (check(i - M + 1))
                    return i - M + 1;
            }
        }
        return N; //未找到匹配
    }

}
